package com.leetcode.ask;

import java.util.HashMap;
import java.util.Map;

/**
 * @ProjectName: leetcode
 * @Package: com.leetcode.ask
 * @description: 5. 最长回文子串
 * 第5题
 * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
 * <p>
 * 示例 1：
 * <p>
 * 输入: "babad"
 * 输出: "bab"
 * 注意: "aba" 也是一个有效答案。
 * 示例 2：
 * <p>
 * 输入: "cbbd"
 * 输出: "bb"
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-palindromic-substring
 * @Author: liyc
 * @CreateDate: 2020/1/8 11:09 AM
 * @Version: 1.0
 * <p>Copyright: Copyright (c) 2020</p>
 */
public class LongestPalindrome {

    /**
     * @param
     * @return
     * @description 自己解法, 暴力法，在LeetCode超时了
     * @author liyc
     * @date 2020/1/8
     */
    public static String longestPalindrome(String s) {
        if ("".equals(s)) {
            return "";
        }
        if (s.length() == 1) {
            return s;
        }
        if (s.length() == 2 && s.charAt(0) != s.charAt(1)) {
            return "" + s.charAt(0);
        }
        char[] arr = s.toCharArray();

        Map<Integer, String> map = new HashMap<>();
        int len = 0;
        for (int i = 0; i < arr.length - 1; i++) {
            StringBuilder str = new StringBuilder();
            str.append(arr[i]);
            for (int j = i + 1; j < arr.length; j++) {
                str.append(arr[j]);
                if (isPalindrome(str.toString())) {
                    String r = str.toString();
                    if (r.length() > len) {
                        map.put(r.length(), r);
                        len = r.length();
                    }
                }
            }
        }

        if (len == 0) {
            return "" + s.charAt(0);
        } else {
            return map.get(len);
        }


    }


    /**
     * @param
     * @return
     * @description 官方解法改进版，利用递归找回文，注意sout要去掉，否则会增加耗时
     * @author liyc
     * @date 2020/1/8
     */
    public static String longestPalindrome2(String s) {
        if ("".equals(s)) {
            return "";
        }
        if (s.length() == 1) {
            return s;
        }
        if (s.length() == 2 && s.charAt(0) == s.charAt(1)) {
            return s;
        }

        if (s.length() == 2 && s.charAt(0) != s.charAt(1)) {
            return "" + s.charAt(0);
        }
        String reverseStr = new StringBuilder(s).reverse().toString();

        char[] heng = s.toCharArray();
        char[] shu = reverseStr.toCharArray();
        int[][] dt = new int[heng.length][shu.length];
        int hIdx = 0;
        int sIdx = 0;
        int max = 0;
        for (int i = 0; i < heng.length; i++) {
            for (int j = 0; j < shu.length; j++) {
                if (heng[i] == shu[j]) {
                    if (i == 0 || j == 0) {
                        dt[i][j] = 1;
                    } else {
                        dt[i][j] = dt[i - 1][j - 1] + 1;
                        if (dt[i][j] > max) {
                            max = dt[i][j];
                            hIdx = i;
                            sIdx = j;
                        }
                    }
                } else {
                    dt[i][j] = 0;
                }
//                System.out.print(dt[i][j]);
            }

//            System.out.println();
        }


        String res = s.substring(hIdx - max + 1, hIdx + 1);
        if (isPalindrome(res)){
            return res;
        }else {
            s = s.replaceAll(res,"");
            return longestPalindrome2(s);
        }


    }


    public static boolean isPalindrome(String x) {
        String reverseNumber = new StringBuilder(x).reverse().toString();
        return reverseNumber.equals(String.valueOf(x));
    }

    public static void main(String[] args) {
        String str = "civilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth";
        long start = System.currentTimeMillis();
        String sub = longestPalindrome2(str);
        long cost = (System.currentTimeMillis() - start);
        System.out.println(cost);
        System.out.println(sub);
    }
}
